package list;

public class RingLinkedList {
    public static void main(String[] args) {
        Node head = new Node((int)(Math.random()*10)+1);
        head.next = new Node((int)(Math.random()*10)+1);
        head.next.next = new Node((int)(Math.random()*10)+1);
        head.next.next.next = new Node((int)(Math.random()*10)+1);
        head.next.next.next.next = new Node((int)(Math.random()*10)+1);

        head.next.next.next.next.next = head.next; //形成环，从末尾节点应用前面的节点

        boolean b = hasCircle(head);
        System.out.println("是否有环：" + b);
    }

    private static boolean hasCircle(Node head) {
//        Node fast = head;
//        Node slow = head;
//        while (fast != null && fast.next != null) {
//            fast = fast.next.next;    //--------------------如果不判断fast.next  这里有可能发生空指针异常
//            slow = slow.next;
//            if (fast == slow) {
//                return true;
//            }
//        }
//        return false;

        Node slow = head;
        Node fast = head;
        while (fast != null && slow != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    static class Node {
        int value;
        Node prev;
        Node next;

        Node(int value) {
            this.value = value;
        }
    }
}
